package sort;

import java.util.Arrays;

public class ShellSort extends Sort {
    @Override
    public void sort(Comparable[] arr) {
        int length = arr.length;
        //定义间隔数
        int h = 1;
//        while(h<length/3)
//            h = h*3+1;//1,4,13,40,121,364,1093,...，表达式可以自己定，+1是为了保证最后的间隔能成为1

        //这里使用一个自定义序列进行分组,也可以如上边注释的实时计算一个从1开始递增的数列
        int[] incr_arr = {1,2,5};
        for(int m=incr_arr.length-1;m>=0;m--){
            h = incr_arr[m];
            //外层循环根据分组数(length-h)来确定需要进行插入排序的次数
            for (int i = h; i < length; i++) {

                for (int j = i; j >= h; j -= h) {
                    if (less(arr[j], arr[j - h]))
                        exch(arr, j, j - h);
                }
            }
            System.out.println("间隔="+h+"分组时，整理后的数组="+ Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        Sort sort = new ShellSort();
        Integer[] arr = {49,38,65,97,76,13,27,49,55,4};
        sort.sort(arr);
        sort.show(arr);
    }
}
